# class Solution(object):
#     def minSwapsCouples(self, row):
#         n = len(row) // 2
#         ans = 0
#         for i in range(n):
#             if row[2 * i] // 2 == row[2 * i + 1] // 2:
#                 continue
#             else:
#                 for j in range(2 * (i + 1), 2 * n):
#                     if row[j] // 2 == row[2 * i] // 2:
#                         row[j], row[2 * i + 1] = row[2 * i + 1], row[j]
#                         ans += 1
#                         break
#         return ans

# 并查集
class Solution(object):
    def minSwapsCouples(self, row):
        n = len(row) // 2
        p = [i for i in range(n)]

        def find(x):
            if p[x] == x:
                return p[x]
            else:
                p[x] = find(p[x])
                return p[x]

        def union(x, y):
            rootx = find(x)
            rooty = find(y)
            if rootx != rooty:
                if rootx < rooty:
                    p[rooty] = rootx
                else:
                    p[rootx] = rooty

        for i in range(n):
            v1 = row[2 * i] // 2
            v2 = row[2 * i + 1] // 2
            union(v1, v2)
        for i in range(n):
            p[i] = find(i)
        t = len(set(p))
        return n - t


data = Solution()
row = [0, 2, 4, 6, 7, 1, 3, 5]
print(data.minSwapsCouples(row))
